package com.backpack;

/**
 * 判断子序列
 * 输入：s = "abc", t = "ahbgdc"
 * 输出：true
 */
public class IsSubsequence0118_392 {
    public boolean isSubsequence(String s, String t) {
        //        暴力可解
        //动态规划思路    相当于 求最长公共子序列的长度，如果长度==s.length() ，则 true
        //dp 含义：表示以[i-1]为结尾的t，和以[j-1]为结尾的s，   的两个子字符串的最长公共子序列的长度
        int[][] dp = new int[t.length()+1][s.length()+1];

        //返回值：dp最大值==s.length()
        int len = 0;
        //初始化 0

        for (int i = 1; i <= t.length(); i++) {
            for (int j = 1; j <= s.length(); j++) {
                if(t.charAt(i-1) == s.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
                len = Math.max(len,dp[i][j]);
            }
        }
        return len == s.length();
    }
}
